In the field of computer graphics, texture mapping is a known technique used to create the appearance of complexity on the surface of rendered objects without actually having to model every detail of the object's surface. Typically, the technique involves mapping a two-dimensional function or array (the texture) onto an object in three-dimensional object space and then projecting the resultant image back to two-dimensional screen space for display. The phrase “texture map” refers to the function or array that is used in the texture mapping process. A common two-dimensional texture map might consist of a repeatable pattern for representing a material, such as wood or marble for example. Three-dimensional texture maps are also used, but not as frequently. Three-dimensional texture maps are usually larger than two-dimensional texture maps. Texture maps are made up of a plurality of numerical values called texels. A texel's numerical value usually corresponds to an RGB color value and perhaps also to an alpha transparency value. (Other parameters may be included in texture maps in addition to, or in lieu of, RGB and alpha values.) A texel's location within a texture map may be designated using s,t coordinates.
A technique known as MIP mapping is also used in texture mapping. MIP mapping involves down-sampling a base texture map numerous times to develop a series of smaller texture maps, each of which represents the base map at a predetermined lower level of resolution. Typically, a map number is assigned to each map. For example, for a system in which two textures were stored, each at four different levels of resolution, eight unique map numbers would be required to refer to the texture maps individually. In systems that use MIP mapping, not only must the base map for each texture be stored in memory, but so must each of the down-sampled maps for each texture. Thus, while texture maps yield important efficiencies for rendering complex images, they can become burdensome in terms of the amount of memory that is required to store them. Indeed, the size of the texture maps used to render an image can in some cases be larger than the rendered image itself.
One technique now being used to address the storage problem associated with texture maps is to store the texture maps in the system memory of the host computer rather than in a dedicated texture memory located within the graphics subsystem. This new technique is beneficial to the extent that it eliminates or reduces the need for a large, dedicated texture memory in the graphics subsystem. On the other hand, this new technique also creates a new problem for systems that utilize hardware rendering instead of software rendering: The rendering hardware of the graphics subsystem may make frequent use of the system bus to access large amounts of texture data stored in system memory. This places significant bandwidth demands on both the system bus and system memory.
Because of these memory space and bandwidth problems associated with texture mapping, it has become popular to logically partition stored texture maps into a number of equally-sized blocks. This is done because it is usually more efficient from a bus and memory utilization point of view to retrieve an entire block of texture data from system memory than to retrieve one texel at a time.
For the same reasons, it has also become popular to store texture maps in a compressed format. Various compression algorithms have been used for this purpose including JPEG, run-length encoding, Huffman encoding, vector quantization and Lempel-Ziv compression. Each of these algorithms may be classified in a number of different ways: First, is the algorithm lossy or lossless? Lossy algorithms frequently yield better compression rates than lossless ones, but they do so at the expense of image quality. Second, does the algorithm produce a compression ratio that is fixed or variable? In other words, will the algorithm compress every portion of an image to the same degree, or will it compress highly detailed portions of the image to a lesser degree than other portions of the image? Another factor of importance in choosing compression algorithms is whether and how easily the compressed texture data produced by the algorithm may be accessed randomly. It is often difficult to determine in advance how a given renderer will access a texture. Therefore, the ability to randomly access compressed texture data is extremely beneficial.
Yet another technique that has become popular is a combination of the above-described methods: A texture map may be logically partitioned into blocks, and then compressed one block at a time. If the compressed texture map is stored in system memory as a set of individual compressed blocks, then a desired piece of texture data may be retrieved from system memory by retrieving only the individual compressed block that contains the desired data. Using this technique, the entire compressed texture map does not have to be retrieved from memory simply to access an individual piece of texture data within it. Moreover, because the block is retrieved in compressed format, additional bus and memory bandwidth savings are realized.
One difficulty that arises when applying the foregoing methods is that of selecting an appropriate compression format for a particular block. Certain compression algorithms work better with certain types of data. For example, certain textures lend themselves to more effective compression using certain texture compression algorithms due to the specific colors or various other aspects associated with the texture data. To date, conventional texture compression algorithms apply the same compression algorithm to all blocks of texture data, irregardless of the various characteristics of the texture data.